#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(NULL));
        return qsortFind(nums, 0, nums.size()-1, k);
    }

    int qsortFind(vector<int>& nums, int begin, int end, int k)
    {
        if(begin == end)
            return nums[begin];
        int key = getRandom(nums, begin, end);
        int left = begin-1, right = end+1, cur = begin;
        while(cur < right)
        {
            if(nums[cur] < key)
                swap(nums[cur++], nums[++left]);
            else if(nums[cur] == key)
                cur++;
            else
                swap(nums[cur], nums[--right]);
        }

        int b = right-left-1, c = end-right+1;
        if(c >= k)
            return qsortFind(nums, right, end, k);
        else if(b+c >= k)
            return key;
        else
            return qsortFind(nums, begin, left, k-b-c);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand()%(right-left+1)+left];
    }
};